
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
  <meta charset="utf-8">
  <title>Introduction To Performance Optimization - Yebangyu's Blog</title>
  <meta name="author" content="Yebangyu">

  
  <meta name="description" content="本文详细分析了如何做性能优化（Performance Optimization）">
  <meta name="keywords" content="Performance Optimization 性能优化 性能 c++ linux perf">

  <!-- http://t.co/dKP3o1e -->
  <meta name="HandheldFriendly" content="True">
  <meta name="MobileOptimized" content="320">
  <meta name="viewport" content="width=device-width, initial-scale=1">

  
  <link rel="canonical" href="http://www.yebangyu.org/blog/2016/04/22/optimization/">
  <link href="/favicon.png" rel="icon">
  <link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
  <link href="/atom.xml" rel="alternate" title="Yebangyu's Blog" type="application/atom+xml">
  <script src="/javascripts/modernizr-2.0.js"></script>
  <script src="//ajax.lug.ustc.edu.cn/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
  <script>!window.jQuery && document.write(unescape('%3Cscript src="/javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
  <script src="/javascripts/octopress.js" type="text/javascript"></script>
  <!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>

  

</head>

<body   >
  <header role="banner"><hgroup>
  <h1><a href="/">Yebangyu's Blog</a></h1>
  
    <h2>Fond of Concurrency Programming and Machine Learning</h2>
  
</hgroup>

</header>
  <nav role="navigation"><ul class="subscription" data-subscription="rss">
  <li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
  
</ul>
  
<form action="https://www.google.com/search" method="get">
  <fieldset role="search">
    <input type="hidden" name="sitesearch" value="www.yebangyu.org">
    <input class="search" type="text" name="q" results="0" placeholder="Search"/>
  </fieldset>
</form>
  
<ul class="main-navigation">
  <li><a href="/">Blog</a></li>
  <li><a href="/blog/archives">Archives</a></li>
  <li><a href="/about">About Me</a></li>
</ul>

</nav>
  <div id="main">
    <div id="content">
      <div>
<article class="hentry" role="article">
  
  <header>
    
      <h1 class="entry-title">Introduction To Performance Optimization</h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-04-22T23:13:13+08:00'><span class='date'><span class='date-month'>Apr</span> <span class='date-day'>22</span><span class='date-suffix'>nd</span>, <span class='date-year'>2016</span></span> <span class='time'>11:13 pm</span></time>
        
      </p>
    
  </header>


<div class="entry-content"><h2 id="section">写在最前</h2>

<p>本文针对<strong>C++</strong>和<strong>linux</strong>环境，但是思想和方法，却对其他语言和环境同样适用。很可供参考的。</p>

<h2 id="section-1">优化前</h2>

<p>1，确定优化是必须要做的。</p>

<p>如果程序已经跑的足够快了，内存使用也足够省了，那么完全没有优化的必要。什么是足够呢？能够满足当前的业务和需求。因此，如果不是绝对必要，不要优化。</p>

<p>这是因为虽然优化不是万恶之源，但是优化可能会带来问题。为了提升一点点性能就得绞尽脑汁、辗转反侧；它可能让之前只需要一两行逻辑很清晰的代码，变成很难理解的高度优化的实现。优化很多时候某种程度上让代码可读性和可维护性变差。</p>

<p>2，确定该做的优化都做了</p>

<!--more-->

<p>有两个方法可以免费地、快速地提高效率：</p>

<p>第一个是使用<strong>release</strong>模式。如果您的程序在<strong>debug</strong>模式下表现不佳，那么可以尝试使用<strong>release</strong>模式进行编译链接。一般说来，这也是发布程序的默认模式。</p>

<p>第二是开启编译器优化。例如<strong>g++</strong>就提供了多个级别的优化选项，一般使用<strong>O2</strong>。</p>

<p>3，确定做了优化前的准备工作</p>

<p>最重要的一点是对程序的性能进行详细分析，找出瓶颈段<strong>（hot spot</strong>）。这很重要，否则，可能导致在错误的方向上越走越远。例如一个程序由函数<strong>f</strong>和<strong>g</strong>构成，<strong>f</strong>花费了<strong>2s</strong>，<strong>g</strong>花费了<strong>100ns</strong>，那您把<strong>g</strong>从<strong>100ns</strong>优化为<strong>20ns</strong>，对系统又有什么帮助呢？<strong>f</strong>才是大头啊。</p>

<p>因此，这里就会有三个问题：</p>

<p>第一，如何定位程序瓶颈段？</p>

<p>要是有一个工具，能够告诉我系统模块的开销比例，那就太好了。有这样的工具吗？有的。<strong>Linux</strong>下的<strong>perf</strong>就是。<a href="https://www.ibm.com/developerworks/cn/linux/l-cn-perf1/">这里</a>是对<strong>perf</strong>非常好的<strong>tutorial</strong>，强烈建议初学者阅读。简单说来，一条命令即可：</p>

<pre><code>sudo perf record -g ./yourprograme
</code></pre>

<p>第二，我想给我的程序的某个函数计时，应该怎么做？</p>

<p>有很多方法，强烈建议您阅读我的<a href="http://www.yebangyu.org/blog/2016/01/07/timingcprograminlinux/">这篇</a>博客，很可供参考。我个人比较喜欢用<strong>timespec</strong>，原因是：知道它的人不多；它可以精确到纳秒；它不受系统时钟的影响（<strong>gettimeofday</strong>显然会，因为它就是读取系统时钟嘛）。</p>

<p>第三，优化后，函数变快了，系统变快了多少？</p>

<p>哦，回忆一下我们本科计算机体系结构里的<strong>Amdahl</strong>定律。如果您没学过这个定律，或者早已还给老师，那么<a href="https://en.wikipedia.org/wiki/Amdahl%27s_law">这里</a>的内容可能对您有帮助。</p>

<h2 id="section-2">优化中</h2>

<p>一旦确定要优化，并且定位了瓶颈段，那么就是想尽一切办法进行加速了。个人总结的一些比较有效的思路和方法：</p>

<p>0，<strong>cache friendly access pattern</strong></p>

<p>尽可能利用<strong>cache</strong>，编写<strong>cache friendly</strong>代码。例子，比如说非常著名的二维数组按行按列访问问题。</p>

<p>1，算法和数据结构层面</p>

<p>使用合适的、高效的数据结构和算法，往往能带来很大的提升。不过，前提是，您需要对您的需求进行认真分析。<strong>find、search、insert、successor、del、min、max</strong>这些操作，哪些是您期望需要非常高效的？哪些操作是您业务里经常出现的？</p>

<p>您需要对以下数据结构和算法有所了解：</p>

<p>哈希表：<strong>O(1)</strong>期望查找时间让它常常成为除了数组之外的首选，尤其是当查找非常关键时。只知道<strong>Separate Chaining</strong>和<strong>Open Addressing</strong>？那您<strong>out</strong>了。建议您阅读我的<a href="http://www.yebangyu.org/blog/2015/12/19/cuckoo-hashing/">这篇</a>讲解<strong>cuckoo hashing</strong>的博客。</p>

<p>跳表：说到<strong>O(lgn)</strong>的<strong>insert、find、del</strong>，很多人想到二叉搜索树，由于非平衡的二叉搜索树有退化为<strong>O(n)</strong>的风险，因此很多场景需要平衡树。<strong>B</strong>树？红黑树？太<strong>heavy</strong>了。有时候，您需要跳表，真的，很需要。它足够简单，而且很多时候就能满足您的需求。除此之外，<strong>Treap</strong>也是一种随机的数据结构，我实现的大规模分布式数据库<a href="https://github.com/yebangyu/Soupen">Soupen</a>里就有提供相应的实现，您可以参考我的这篇<a href="http://www.yebangyu.org/blog/2016/05/07/treappkskiplist/">博客</a>。</p>

<p><strong>Sunday</strong>算法：字符串匹配里，<strong>KMP</strong>算法是大名鼎鼎了。谁让<strong>Knuth</strong>是大佬呢？可是，您是否知道<strong>Sunday</strong>算法？<strong>Sunday</strong>算法什么时候会比<strong>KMP</strong>高效而且高效地多？</p>

<p><strong>string.h</strong>里提供的算法：包括<strong>memcmp、memcpy、memmem、memmove</strong>等。当您想手工实现这些函数，正在写一大堆<strong>while</strong>循环时，请优先选择这些库函数。</p>

<p>排序算法：快速排序，非常常见、常用。那么，如何编写一个高效的快速排序？建议您阅读我的<a href="http://www.yebangyu.org/blog/2016/03/09/quicksort/">这篇</a>博客。</p>

<p>2，将小但是频繁调用的函数内联。注意，<strong>gcc</strong>有提供强制内联的<strong>feature</strong>，也就是<code>__attribute__((always_inline))</code></p>

<p>3，为分支预测适当加上<strong>likely</strong>或者<strong>unlikely</strong>。请注意，<strong>if</strong>语句并不可怕，可怕的是分支预测失败。这正和锁并不可怕一样，因为加锁和释放锁其实很快，可怕的是锁冲突。所以，您需要了解这两组宏：</p>

<pre><code>#define  likely(x)        __builtin_expect(!!(x), 1) 
#define  unlikely(x)      __builtin_expect(!!(x), 0) 
</code></pre>

<p>4，消除<strong>if</strong>语句。比如说如下代码：</p>

<pre><code>if (a &gt; 0 ) b += 2; else b+= 1;
</code></pre>

<p>那么可以消除为<code>b += 1 + (a &gt; 0);</code></p>

<p>5，查表法。将反复使用的、不大的、静态的数据事先计算好，存在表格里，需要的时候，直接去查，避免计算。</p>

<p>还有很多很多。就看您的知识面和经验了。</p>

<p>有一个错误的想法，很值得在这里说。很多资料上写着：用移位代替乘除法。因此很多人的代码里充斥着大量的<code>&gt;&gt;1</code> 以及 <code>&lt;&lt;1</code>，美其名曰性能优化。</p>

<p>事实上，现在的编译器很聪明了，一点都不傻，不信您可以直接写<code>a / 2</code> 然后看看开启<strong>-O2</strong>选项后的汇编代码。结果会让您赞叹的。上面的左移一位、右移一位没有任何必要。</p>

<p>正常情况下，请按照逻辑需要直接写代码。现代编译器真的已经很牛逼了。因此，您应该重点关注算法、<strong>Cache</strong>、分支预测等层面。</p>

<h2 id="section-3">优化后</h2>

<p>优化后，请记得再次对您的程序进行<strong>profiling</strong>，确保优化是有效的。</p>

<p>别偏听偏信，别坚信<strong>KMP</strong>一定比暴力算法快，别盲信教科书、博客、资料里的说法，别跪舔大佬！请实际测试！测试！！再测试！！！</p>

<p>一切以您的环境、以您的系统、以您的测试为准。没有权威。</p>

<h2 id="section-4">参考资料</h2>

<p>专门针对<strong>C++</strong>和<strong>Linux</strong>的优化的书，不多。但是有一些零碎的、七七八八的资料，编程珠玑啊，深入理解计算机系统啊，还有最近刚刚出版的<strong>optimized c++</strong>啊等等。</p>

<p>有好心的网友在Github上维护了一个<a href="https://github.com/fenbf/AwesomePerfCpp">项目</a>，分享了不少C++性能优化相关的资料。</p>

</div>


  <footer>
    <p class="meta">
      
  

<span class="byline author vcard">Posted by <span class="fn">Yebangyu</span></span>

      




<time class='entry-date' datetime='2016-04-22T23:13:13+08:00'><span class='date'><span class='date-month'>Apr</span> <span class='date-day'>22</span><span class='date-suffix'>nd</span>, <span class='date-year'>2016</span></span> <span class='time'>11:13 pm</span></time>
      

<span class="categories">
  
    <a class='category' href='/blog/categories/xing-neng-you-hua/'>性能优化</a>
  
</span>


    </p>
    
      <div class="sharing">
  
  
  
</div>

    
    <p class="meta">
      
        <a class="basic-alignment left" href="/blog/2016/04/10/stringliteralincpp/" title="Previous Post: String Literal In C++">&laquo; String Literal In C++</a>
      
      
        <a class="basic-alignment right" href="/blog/2016/05/01/hanwudi/" title="Next Post: 论汉武帝独尊儒术">论汉武帝独尊儒术 &raquo;</a>
      
    </p>
  </footer>
</article>


</div>

<aside class="sidebar">
  
    <section>
  <h1>Recent Posts</h1>
  <ul id="recent_posts">
    
      <li class="post">
        <a href="/blog/2017/03/11/2017/">2017技术成长之路</a>
      </li>
    
      <li class="post">
        <a href="/blog/2017/02/17/virtualfunctionandvariadicparametertemplate/">虚函数和变长参数模板的妙用</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/25/singleton/">Singleton与多线程</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/04/introductiontohazardpointer/">Lock Free中的Hazard Pointer(下)</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/03/gccandperfopt/">性能优化的那些传说和迷思</a>
      </li>
    
  </ul>
</section>
<section>
  <h1>Friends' Link</h1>
  <ul>
    <li>
	  <li><a href="http://www.chongh.wiki/">Diting0x</a></li>
	  <li><a href="http://www.xiaolili.net/">wangli</a></li>
	  <li><a href="http://www.skykewei.top">dukewei</a></li>
	  <li><a href="http://irwenqiang.github.io">chenwenqiang</a></li>
      <li><a href="http://www.armsword.com">duruofei</a></li>
    </li>
  </ul>
</section><section>
  <h1>Yebangyu</h1>
  <p>福建人。热爱历史、K歌、NBA</p>
  <p>帝都码农</p>
  <p>历史学家，专治秦汉史</p>
</section>
<section>
 <h1>Categories</h1>
 <ul id="categories">
  <li class='category'><a href='/blog/categories/c-plus-plus/'>c++ (11)</a></li>
<li class='category'><a href='/blog/categories/soupen/'>soupen (4)</a></li>
<li class='category'><a href='/blog/categories/web/'>web (1)</a></li>
<li class='category'><a href='/blog/categories/qi-ta/'>其他 (5)</a></li>
<li class='category'><a href='/blog/categories/li-shi/'>历史 (2)</a></li>
<li class='category'><a href='/blog/categories/bing-xing-bian-cheng/'>并行编程 (20)</a></li>
<li class='category'><a href='/blog/categories/xing-neng-you-hua/'>性能优化 (2)</a></li>
<li class='category'><a href='/blog/categories/suan-fa/'>算法 (4)</a></li>
<li class='category'><a href='/blog/categories/bian-yi-lian-jie/'>编译链接 (2)</a></li>

 </ul>
</section>




  
</aside>


    </div>
  </div>
  <footer role="contentinfo"><!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>
<p>
  Copyright &copy; 2017 - Yebangyu -
  <span class="credit">Powered by <a href="http://octopress.org">Octopress</a></span>
</p>
<script type="text/javascript">var cnzz_protocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1257548193'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s11.cnzz.com/z_stat.php%3Fid%3D1257548193' type='text/javascript'%3E%3C/script%3E"));</script>

</footer>
  











</body>
</html>
